#define _CRT_SECURE_NO_WARNINGS 1

//#include <bits/stdc++.h>
//using namespace std;
//#include <iostream>
//#include <algorithm>
//const int MAXN = 100005;
//
//int n, m, x;
//long long a[MAXN];
//int b[MAXN];
//int cap[MAXN];
//
//const long long INF = 1e18;
//
//struct Node 
//{
//    int l, r;
//    long long min_val;
//    int idx;
//} tree[4 * MAXN];
//
//void push_up(int u) 
//{
//    int left = u << 1;
//    int right = u << 1 | 1;
//    if (tree[left].min_val <= tree[right].min_val) 
//    {
//        tree[u].min_val = tree[left].min_val;
//        tree[u].idx = tree[left].idx;
//    }
//    else 
//    {
//        tree[u].min_val = tree[right].min_val;
//        tree[u].idx = tree[right].idx;
//    }
//}
//
//void build_tree(int u, int l, int r) 
//{
//    tree[u].l = l;
//    tree[u].r = r;
//    if (l == r) 
//    {
//        tree[u].min_val = a[l];
//        tree[u].idx = l;
//        return;
//    }
//    int mid = (l + r) >> 1;
//    build_tree(u << 1, l, mid);
//    build_tree(u << 1 | 1, mid + 1, r);
//    push_up(u);
//}
//
//void update(int u, int pos, long long val)
//{
//    if (tree[u].l == tree[u].r) 
//    {
//        tree[u].min_val = val;
//        return;
//    }
//    int mid = (tree[u].l + tree[u].r) >> 1;
//    if (pos <= mid) update(u << 1, pos, val);
//    else update(u << 1 | 1, pos, val);
//    push_up(u);
//}
//
//Node query(int u, int l, int r) 
//{
//    if (l <= tree[u].l && tree[u].r <= r) 
//    {
//        return tree[u];
//    }
//    int mid = (tree[u].l + tree[u].r) >> 1;
//    Node res;
//    res.min_val = INF;
//    if (l <= mid) 
//    {
//        Node left_res = query(u << 1, l, r);
//        if (left_res.min_val < res.min_val) res = left_res;
//    }
//    if (r > mid) 
//    {
//        Node right_res = query(u << 1 | 1, l, r);
//        if (right_res.min_val < res.min_val) res = right_res;
//    }
//    return res;
//}
//
//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    cin >> n >> m >> x;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    for (int i = 0; i < m; i++) cin >> b[i];
//    sort(b, b + m);
//    for (int i = 1; i <= n; i++) cap[i] = x;
//    build_tree(1, 1, n);
//    long long ret = 0;
//    for (int i = 0; i < m; i++) 
//    {
//        int d = b[i];
//        Node res = query(1, 1, d);
//        if (res.min_val == INF)  continue;
//        int idx = res.idx;
//        ret += a[idx];
//        cap[idx]--;
//        if (cap[idx] == 0) update(1, idx, INF);
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include <iostream>
//#include <unordered_map>
//using namespace std;
//
//int main() 
//{
//    int n;
//    cin >> n;
//    unordered_map<long long, int> count;
//    count[0] = 1;
//    long long s = 0;
//    long long ret = 0;
//    for (int i = 0; i < n; i++) 
//    {
//        long long a;
//        cin >> a;
//        s += a - 1;
//        if (count.find(s) != count.end()) ret += count[s];
//        count[s]++;
//    }
//    cout << ret << endl;
//    return 0;
//}

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        unordered_set<string> hash;
        for (auto& str : wordDict) hash.insert(str);

        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        s = " " + s;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

class Solution
{
    const int INF = 0x3f3f3f3f;
public:
    int coinChange(vector<int>& coins, int amount)
    {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, INF));
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= amount; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j - coins[i - 1] >= 0) dp[i][j] = min(dp[i][j], dp[i][j - coins[i - 1]] + 1);
            }
        }

        return dp[n][amount] == INF ? -1 : dp[n][amount];
    }
};